package leetcode;

public class LongestPalindrome {

	public static void main(String[] args) {
		LongestPalindrome object = new LongestPalindrome();
		object.longestPalindrome("abccccdd");
	}
	//Given a string which consists of lowercase or uppercase letters, 
	//find the length of the longest palindromes that can be built with those letters.
	public int longestPalindrome(String s) {
		if (s == null || s.length() <= 0) {
			return 0;
		}
		char[] chas = s.toCharArray();
		int[] chasCount = new int[256];
		//记录所有字符出现的次数
		for (int i = 0; i < chas.length; i++) {
			chasCount[chas[i]]++;
		}
		int maxLength = 0;
		boolean addOne = false;
		for (int i = 0; i < chasCount.length; i++) {
			if ((chasCount[i] & 1) == 0) {
				//如果是偶数可以全部加
				maxLength += chasCount[i];
			} else {
				//对于奇数而言，必须得留1，但是由于可以构造成奇数长的回文串，所以还可以加1
				//addOne表示已经使用了，注意不能最后去加1以图简便，因为可能没有奇数的
				if (!addOne) {
					maxLength += chasCount[i];
					addOne = true;
				} else {
					maxLength += chasCount[i] - 1;
				}
			}
		}
		System.out.println("maxLength" + maxLength);
		return maxLength;
	}
}
